When messages are transmitted over a communication network, errors in transmission may occur. To detect and correct these errors, each transmitted message is modified, adding a pre-determined error-correcting scheme to the message. After the message is received, the message must be decoded.
Common types of codes used include block codes, such as Reed-Solomon and Bose Chaudhuri Hocquenghem (BCH) codes. BCH codes are a commonly used multi-level cyclic variable length code used in error correction schemes.
The encoded message is normally grouped by codeword. A codeword is generally comprised of n symbols, further comprising k information symbols, which results in n−k redundant symbols. For BCH codes, n=2m−1, and k≧n−mt. To correct for t bits, at most mt bits of redundancy are needed.
U.S. patent application Ser. No. 09/976,731, entitled “LOW COMPLEXITY AND LOW POWER FEC SUPPORTING HIGH SPEED PARALLEL DECODING OF SYNDROME-BASED FEC CODES,” discloses a method of reducing power consumption and complexity when performing forward error correction by using parallel decoding techniques. The present invention is not designed to process error codes using parallel decoding techniques. U.S. patent application Ser. No. 09/976,731 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/092,407, entitled “SIGNAL PROCESSING METHOD, SIGNAL PROCESSING SYSTEM, PROGRAM FOR SIGNAL PROCESSING, AND COMPUTER-READABLE STORAGE MEDIUM ON WHICH THIS PROGRAM IS RECORDED,” discloses a signal processing method for processing 40 Gbps or higher communication signals. The method calculates a Yule-Walker equation that has elements of a Galois field, and solves the equation using Jacobi's formula to obtain symmetric matrices. The number of errors is determined to be the maximum matrix size that corresponds to the non-zero solution. The method then determines if the number of errors equals the number of correctable errors. The present invention does not determine the number of errors and decide if the number of errors is correctable. U.S. patent application Ser. No. 10/092,407 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/202,252, entitled “EFFICIENT DECODING OF PRODUCT CODES,” discloses a decoding system that generates test pattern syndrome and subsequent test pattern syndromes using a recursive function of the syndromes previously generated. The present invention does not generate syndromes using a recursive function of the syndromes previously generated. U.S. patent application Ser. No. 10/202,252 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/301,769, entitled “ERROR CORRECTION IMPROVEMENT FOR CONCATENATED CODES,” discloses a multiple dimension codeword. Decoding is performed in multiple passes for each dimension, wherein the corrected data of the previous pass used as an input to subsequent passes. The present invention does not encode data in multiple dimensions. U.S. patent application Ser. No. 10/301,769 is hereby incorporated by reference into the specification of the present invention.
Known non-patent publications include:
Error Control Coding, Fundamentals and Applications, Chapter 6: Binary BCH Codes, Shu Lin and Daniel J. Costello, Jr., Pearson Prentice Hall, second edition, pp. 194-195, 224-225, 2004; and
A Simple Decoding of BCH Codes over GF(2m), Keiichiro Kogo, IEEE Transactions on Communications, vol. 46, no. 6, June 1998.